package leetcode;

import Tree.CreateByPreAndIn;
import Tree.TreeNode;

public class HouseRobber {

	public static void main(String[] args) {
//		int[] nums = {5,4,9,3,6,12,13,5,6,7,4,2,3};
//		HouseRobber robber = new HouseRobber();
//		System.out.println(robber.rob(nums));
//		System.out.println(robber.rob(nums, 0, nums.length - 1));
		int[] pre = { 1, 2, 9, 0, 4, 6, 8, 3, -2, 7, -1, -3, 10, 5, 11 };
		int[] in = { 0, 9, 4, 2, 8, 6, 3, 1, -1, 7, -3, -2, 5, 10, 11 };
		TreeNode root = CreateByPreAndIn.reConstructBinaryTree(pre, in);
		HouseRobber robber = new HouseRobber();
		System.out.println(robber.rob(root));
		System.out.println("the robber help count: " + robber.robHelpCount);
//		robber.rob_3_2(root);
//		System.out.println("the count: " + robber.count);
	}
	
	//house robber I
	//对于非负的整数
	public int rob(int[] nums) {
        if(nums == null || nums.length <= 0){
            return 0;
        }
        int exclude = 0;  //不包含当前元素的最大值
        int exclude_new ;   //更新后的exclude值
        int include = nums[0];  //包含当前元素时的最大值
        int maxSum = 0;
        for(int i = 1; i < nums.length; i++){
            //由于exclude_new是指的不包括当前元素的最大值，所以就等于前一个元素的ex和in中的最大值
            exclude_new = Math.max(exclude, include);  
            include = exclude + nums[i];   //等于不包含前一个元素的最大值 + nums[i](注意，是非负的整数)
            exclude = exclude_new;
        }
        maxSum = Math.max(exclude, include);
        return maxSum;
    }
	
	//house robber II, the house is a cycle, so something changed
	public int rob2(int[] nums) {
		if (nums == null || nums.length <= 0) {
			return 0;
		}
	    if (nums.length == 1){
	    	return nums[0];
	    }
	    return Math.max(rob(nums, 0, nums.length - 2), rob(nums, 1, nums.length - 1));
	}
	
	public int rob(int[] nums, int start, int end){
		int exclude = 0;
		int include = nums[start];
		int exclude_last = 0;
		for(int i = start + 1; i <= end; i++){
			exclude_last = exclude;
			exclude = Math.max(exclude, include);
			include = exclude_last + nums[i];
		}
		return Math.max(include, exclude);
	}
	
	
	//House robber III, the house is the tree(饿了么的笔试题，简直就是不想招人)
	class Sum{
        int father;
        int child;
        public Sum(int father, int child){
            this.father = father;
            this.child = child;
        }
    }
	
	//3ms
    public int rob(TreeNode root) {
        if(root == null){
            return 0;
        }
        Sum res = robHelp(root);
        return Math.max(res.father, res.child);
    }
    
    int robHelpCount = 0;
    
    //这个解法是O(n)
    public Sum robHelp(TreeNode node){
    	robHelpCount++;
        if(node == null){
            return new Sum(0, 0);
        }
        //左右结点都为null
        if(node.left == null && node.right == null){
            return new Sum(node.val, 0);
        }
        //左结点的
        Sum left = robHelp(node.left);
        //右结点
        Sum right = robHelp(node.right);
        int father = Math.max(node.val + left.child + right.child, left.father + right.father);
        System.out.println("the node: " + node.val + "father:" + father);
        System.out.println("the node: " + node.val + "child:" + left.father  + " "+ right.father);
        
        return new Sum(father, left.father + right.father);
    }
    
    
    int count = 0;
    //直接递归，688ms
    public int rob_3_2(TreeNode root) {
    	count++;
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            return root.val;
        }
        int exclude = rob_3_2(root.left) + rob_3_2(root.right);
        int include = root.val;
        
        //这个有太多的冗余，感觉应该是O(2 ^ n)
        //我们这个时候计算root.left.left, 上面求exclude的时候，rob(root.left)又在计算exclude
        //的时候计算了一次root.left.left
        if(root.left != null){
            if(root.left.left != null){
            	include += rob_3_2(root.left.left);
            }
            if(root.left.right != null){
            	include += rob_3_2(root.left.right);
            }
        }
        if(root.right != null){
            if(root.right.left != null){
            	include += rob_3_2(root.right.left);
            }
            if(root.right.right != null){
            	include += rob_3_2(root.right.right);
            }
        }
        return Math.max(include, exclude);
    }
}
